/*
 * @lc app=leetcode.cn id=120 lang=javascript
 *
 * [120] 三角形最小路径和
 */

// @lc code=start
/**
 * @param {number[][]} triangle
 * @return {number}
 */

// f(i,j) 到达节点[i, j]的最小路径和
// var minimumTotal = function(triangle) {
//   // n: 三角形的层数
//   let n = triangle.length;
//   let f = new Array(n);
//   for (let i = 0; i < n; i++) {
//     f[i] = new Array(triangle[i].length);
//   }

//   // 自底向上
//   for (let i = n - 1; i >=0; i--) {
//     for (let j = 0; j < triangle[i].length; j++) {
//       if(i == n -1){
//         // 初始化边界
//         f[i][j] = triangle[i][j];
//       } else {
//         f[i][j] = Math.min(f[i+1][j], f[i+1][j+1]) + triangle[i][j];
//       }
//     }
//   }
//   return f[0][0];
// };

// 滚动数组
var minimumTotal = function(triangle) {
  let n = triangle.length;
  let f = new Array(2);
  for (let i = 0; i < 2; i++) f[i] = new Array(n);

  for (let i = n - 1; i >= 0; i--) {
    let ind = i & 1;
    let pre_ind = (ind + 1) & 1;
    for (let j = 0; j < triangle[i].length; j++) {
      if(i === n - 1) {
        f[ind][j] = triangle[i][j];
      } else {
        f[ind][j] = Math.min(f[pre_ind][j], f[pre_ind][j+1]) + triangle[i][j];
      }
    }
  }
  return f[0][0];
}
// @lc code=end

